/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/continuous-subarray-sum
   @Language: C++
   @Datetime: 16-02-09 05:46
   */

class Solution {
public:
	/**
	 * @param A an integer array
	 * @return  A list of integers includes the index of 
	 *          the first number and the index of the last number
	 */
	vector<int> continuousSubarraySum(vector<int>& A) {
		// Write your code here
		int sum=0, mx=INT_MIN, s=0, e=0;
		vector<int> vs(2,-1);
		for(int i=0; i<A.size(); ++i){
			sum += A[e=i];
			if (mx<sum){
				mx = sum;
				vs[0]=s;
				vs[1]=e;
			}
			if (sum<0){
				sum=0;
				s=e=i+1;	// new subarray start from next
			}
		}
		return vs;
	}
};
